package com.bk.circle;

import com.bk.AbstractList;

public class CircleLinkedList<E> extends AbstractList<E> {

	public Node<E> first;
	public Node<E> last;

	private static class Node<E> {
		E elementE;
		Node<E> prev;
		Node<E> next;

		public Node(Node<E> prev, E elementE, Node<E> next) {
			this.elementE = elementE;
			this.next = next;
			this.prev = prev;
		}

		public String toString() {
			StringBuilder sb = new StringBuilder();
			if (prev != null) {
				sb.append(prev.elementE);
			} else {
				sb.append("null");
			}
			sb.append("_").append(elementE).append("_");
			if (next != null) {
				sb.append(next.elementE);
			} else {
				sb.append("null");
			}
			return sb.toString();
		}

	}

	private Node<E> node(int index) {
		rangeCheck(index);
		if (index < (size >> 1)) {
			Node<E> node = first;
			for (int i = 0; i < index; i++) {
				node = node.next;
			}
			return node;
		} else {
			Node<E> node = last;
			for (int i = size - 1; i > index; i--) {
				node = node.prev;
			}
			return node;
		}

	}

	@Override
	public void clear() {
		this.first = null;
		this.last = null;
		this.size = 0;
	}

	@Override
	public E get(int index) {
		Node<E> node = this.node(index);
		return node.elementE;
	}

	@Override
	public E set(int index, E element) {
		Node<E> node = this.node(index);
		node.elementE = element;
		return element;
	}

	@Override
	public void add(E element) {
		this.insert(size, element);
	}

	@Override
	public void insert(int index, E element) {
		rangeCheck(index);
		if (index == size) { // index ==size 这个判断已经判断出这个长度是不是0
			Node<E> oldLastNode = last;
			Node<E> newNode = new Node<E>(null, element, null);
			if (last == null) {//
				first = newNode;
				newNode.prev = newNode;
				newNode.next = newNode;
			} else {
				newNode.next = oldLastNode.next;
				newNode.prev = oldLastNode;
				oldLastNode.next = newNode;
				first.prev = newNode;
			}
			last = newNode;
//		} else if (index == 0) {
//			Node<E> oldFirstNode = first;
//			Node<E> newNode = new Node<E>(null, element, null);
//
//			newNode.prev = oldFirstNode.prev;
//			newNode.next = oldFirstNode;
//			oldFirstNode.prev.next = newNode;
//			oldFirstNode.prev = newNode;
//
//			first = newNode;
		} else { // 双向循环链表只要不是空，这个node的前后节点都不会为空
			Node<E> next = node(index);
			Node<E> prev = next.prev;
			Node<E> newNode = new Node<E>(prev, element, next);
			next.prev = newNode;
			prev.next = newNode;
			if (index == 0) {
				first = newNode;
			}
		}
		size++;
	}

	@Override
	public E remove(int index) {
		rangeCheck(index);
		Node<E> newNode = first;
		if (size == 1) {
			first = null;
			last = null;
		} else {
			newNode = node(index);
			Node<E> prev = newNode.prev;
			Node<E> next = newNode.next;
			prev.next = next;
			next.prev = prev;
			if (index == 0) {
				first = next;
			}
			if (index == size - 1) {
				last = prev;
			}
		}

		size--;
		return newNode.elementE;
	}

	@Override
	public int indexOf(E element) {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public String printStr() {
		Node<E> node = first;
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < size; i++) {

			sb.append(node.toString());
			node = node.next;
			sb.append("，");
		}
		sb.append("\n");
		return sb.toString();
	}
}
